//排序数组
/*给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

 */
 class Solution {
public:
    int get_mid(vector<int>& nums, int left, int right) {
        int mid = left + (right - left) / 2;
        if (nums[left] <= nums[right]) {
            if (nums[mid] > nums[right])
                return right;
            else if (nums[mid] < nums[left])
                return left;
            // return mid;
        } else {
            if (nums[mid] > nums[left])
                return left;
            else if (nums[mid] < nums[right])
                return right;
        }
        return mid;
    }
    int quick_sort(vector<int>& nums, int left, int right) {
        int key = get_mid(nums, left, right);
        swap(nums[key], nums[right]);
        int s = left;
        int q = left;
        while (q < right) {
            if (nums[q] < nums[right]) {
                swap(nums[s], nums[q]);
                s++;
            }
            q++;
        }
        swap(nums[right], nums[s]);
        return s;
    }
    void dfs(vector<int>& nums, int left, int right) {
        if (right <= left)
            return;
        // int mid = left + (right - left) / 2;
        int i = quick_sort(nums, left, right);
        dfs(nums, left, i - 1);
        dfs(nums, i + 1, right);
    }
    vector<int> sortArray(vector<int>& nums) {
        dfs(nums, 0, nums.size() - 1);
        return nums;
    }
};